package homework;

/**
 * 0-1背包，计算最大价值  DP方程
 */
public class Gold {
    /**
     * 计算最大价值
     * @param values 物品的价值数组
     * @param peoples 物品的重量数组
     * @param maxPeople 背包最大承重
     * @return
     */
    public static  int maxValue(int[] values,int[] peoples,int maxPeople){
        if(values==null|| values.length==0) return 0;
        if(peoples==null|| peoples.length==0) return 0;
        if(values.length!=peoples.length|| maxPeople<=0) return 0;

        //dp数组  dp[i-1]  i从1开始
        int[][] dp=new int[values.length+1][maxPeople+1];

        for(int num=1;num<=values.length;num++){
            for(int people=1;people<=maxPeople;people++){
                //选择的物品超过最大承重
                if(peoples[num-1]>people){
                    //不能选该物品 等于上轮的最大价值
                    dp[num][people]=dp[num-1][people];
                }
                //选择的物品不超过最大承重
                else{
                    //上轮的最大价值
                    int preValue=dp[num-1][people];
                    //选择该商品后的最大价值
                    int curValue=values[num-1]+dp[num-1][people-peoples[num-1]];
                    //两者取最大值
                    dp[num][people]=Math.max(preValue,curValue);
                }
            }
        }
        int mv=dp[values.length][maxPeople];
        //逆推找出装入背包的所有商品的编号（选的矿的编号）
        int people=maxPeople;
        String numStr="";
        for(int num=values.length;num>0;num--){
            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的（第i个矿挖）
            if(dp[num][people]>dp[num-1][people]){
                numStr = num+" "+numStr;
                //原来重量 - 已经去掉的重量
                people=people-peoples[num-1];
            }
            if(people==0)
                break;
        }
        System.out.println("选择的金矿有："+numStr);

        return mv;

    }

    public static void main(String[] args) {
        //金矿储量
        int[] values={60,30,50,40,60};
        //人数
        int[] peoples={2,2,6,5,4};
        //人数
        int maxPeople=10;
        System.out.println("挖出的最大储量是："+maxValue(values,peoples,maxPeople));
    }
}
